// DepGraph.h

#ifndef _DEPGRAPH_H_
#define _DEPGRAPH_H_

using namespace std;

/** Class for a single node of the dependency graph. */
class GraphNode {

    // fill in your own code here.
 public:
  bool visited;
  int post;
  int size; // add this later

  GraphNode() {
    visited = false;
    post = -999;
  }

};

/** Class for the representation of a dependency graph. */
class DepGraph {

 private:
  std::vector<GraphNode> nodes;
  std::vector<std::vector<int> > adjList;
  std::vector<int> ccnum;
  std::vector<std::vector<int> > scc; // handle creation of inner array properly
  int clock; // see if can be better placed.
  int cc; // see if can be better placed.
  int size;

    // fill in your own code here.
 public:
  DepGraph(int numNodes) {
    // initialize vector nodes to contain numNodes elements -REPLACE
    for(int i = 0; i < numNodes; i++) {
      GraphNode node;
      nodes.push_back(node);
    }

    // also initialize adjList - REPLACE
    adjList.resize(numNodes);
    for(int i = 0; i < numNodes; i++) {
      adjList[i].resize(numNodes);
    }

    // REPL
    ccnum.resize(numNodes);

    clock = 1;
    cc = 0;
    size = numNodes;
  }

  int getSize() {
    return size;
  }

  std::vector<GraphNode> getNodes() {
    return nodes;
  }

  std::vector<std::vector<int> > getAdjList() {
    return adjList;
  }

  void setAdjList(std::vector<std::vector<int> > l) {
    adjList = l;
  }

  // not sure if this will encapsulate the ccnum properly!
  std::vector<int> getCcnum() {
    return ccnum;
  }

  std::vector<std::vector<int> > getScc() {
    return scc;
  }

  DepGraph reverseGraph() {
    // currently not copying. it's just assuming that nodes have nothing new
    // to copy. so, it's simply creating a new graph. - REPLACE
    int size = nodes.size();
    DepGraph rGraph(size);

    // try linear time
    for(int i = 0; i < size; i++) {
      for(int j = 0; j < size; j++) {
	rGraph.adjList[i][j] = !adjList[i][j];
      }
    }

    return rGraph;
  }

  void SCC() {
    DepGraph reverseGraph = this->reverseGraph();
    reverseGraph.DFS(regularOrder(), false);

    DFS(reverseGraph.descPostOrder(), true);
  }

  bool depCycle(int node) {
    if(adjList[node][node] == 1) {
      return true;
    } else {
      return false;
    }
  }

  void DFS(std::vector<int> order, bool ccalg) { // supply the regular/descending post order as an array

    // reset clock and ccnum here??

    for(int i = 0; i < size; i++) {
      nodes[i].visited = false;
    }

    if(ccalg) {
      scc.push_back(std::vector<int>());
    }

    for(int i = 0; i < order.size(); i++) {
      int index = order[i];
      if(!nodes[index].visited) {
	explore(index, ccalg);

	if(ccalg) {
	  cc++;
	  scc.push_back(std::vector<int>());
	}
      }
    }

    /*    for(int i = 0; i < nodes.size(); i++) {
      nodes[i].visited = false;
    }

    for(int i = 0; i < nodes.size(); i++) {
      if(!nodes[i].visited) {
	explore(i);
	cc++;
      }
      }*/
  }

  void explore(int i, bool ccalg) {
    nodes[i].visited = true;
    int size = nodes.size();

    if(ccalg) {
      previsit(i);
    }

    for(int j = 0; j < size; j++) {
      if(adjList[i][j] == 1) { // for each edge from nodes[i] to nodes[j]
	if(!nodes[j].visited) {
	  explore(j, ccalg);
	}
      }
    }

    postvisit(i);

  }

  void previsit(int i) {
    ccnum[i] = cc;
    scc[cc].push_back(i);
  }

  void postvisit(int i) {
    nodes[i].post = clock++;
  }

  // can be called only on a graph on which DFS was run
  std::vector<int> descPostOrder() {
    // sort of like counting sort
    std::vector<int> post;
    post.resize(size);

    for(int i = 0; i < size; i++) {
      post[nodes[i].post - 1] = i; // - 1 because clock starts from 1
    }

    return post;
  }

  std::vector<int> regularOrder() {
    std::vector<int> post;
    post.resize(size);

    for(int i = 0; i < size; i++) {
      post[i] = i;
    }

    return post;
  }

};

#endif
